# -*- coding: utf-8 -*-
"""
Created on Thu Dec 20 23:54:18 2018

@author: Administrator
"""
import sys
sys.path.append("../queue/")
sys.path.append("../stack/")

from seq_queue import SeqQueue
from linked_stack import LinkedStack
from tree_node import BTNode

class ArgumentError(ValueError):
    pass


        
class LinkedBinaryTree:
    """基于链式二叉树
    """
    def __init__(self, data = None):
        # 头指针
        self.head = None
        # 节点数
        self.count = 0
        if data is not None:
            self.head = BTNode(data)
            self.count += 1

 
    def is_empty(self):
        if self.head is None:
            return True
        return False
    
    def set_root(self, root):
        if not isinstance (root, BTNode):
            raise ArgumentError("root argument error!")
        if self.head is not None:
            return
        else:
            self.head = root
            self.count += 1
            
    def set_left(self, left):
        """设置左子树
        """
        if not isinstance(left, LinkedBinaryTree):
            raise ArgumentError("left tree argument error!")
        if not self.is_empty():
            self.head.left = left.head
            self.count += left.count
            
    def set_right(self, right):
        """设置右子树
        """
        if not isinstance(right, LinkedBinaryTree):
            raise ArgumentError("right tree argument error!")
        if not self.is_empty():
            self.head.right = right.head
            self.count += right.count
    
    def count_nodes(self):
        return self.count
            
    def preorder(self, p):
        """先根遍历
        中序遍历、后续遍历只需要调整一下对根节点的处理顺序即可
        """
        result = []
        if p is None:
            return result
        else:
            result.append(p.data)
            result += self.preorder(p.left)
            result += self.preorder(p.right)
            return result
        
    def preorder_nonrec(self, root):
        """先根遍历的非递归实现
        """
        stack = LinkedStack()
        while root is not None or not stack.is_empty():
            while root is not None:
                print(root.data)
                # 保存root非空右子树
                if root.right is not None:
                    stack.push(root.right)
                root = root.left
            # 返回到最近一次右子树的位置，作为当前根节点
            if not stack.is_empty():
                root = stack.pop()
        
    def levelorder(self):
        """层次遍历
        层次遍历是宽度优先策略，使用队列作为中间变量
        """
        # 保存没有被遍历过的节点
        queue = SeqQueue()
        p = self.head
        queue.enqueue(p)
        while not queue.is_empty():
            btnode = queue.dequeue()
            print(btnode.data)
            if btnode.left is not None:
                queue.enqueue(btnode.left)
            if btnode.right is not None:
                queue.enqueue(btnode.right)

if __name__ == '__main__':
    t = LinkedBinaryTree(5)
    left = LinkedBinaryTree(6)
    right = LinkedBinaryTree(9)
    t.set_left(left)
    t.set_right(right)
    
    t.levelorder()